// 场景已知一个几乎有序的数组，几乎有序的意思就是如果想把数组排序好的话，每个元素移动的距离不超过k，k相对于数组来说很小
import PriorityQueue from '../ts手写数据结构/优先队列'
const sorteArrDistanceLessK = (arr: Array<number>,k:number) => {
    const heap:PriorityQueue<number> = new PriorityQueue()
    let index = 0
    for(; index <= Math.min(arr.length, k); index++) {
        heap.add(arr[index])
    }
    let i = 0
    for(; index < arr.length;i++,index++) {
        heap.add(arr[index])
        arr[i] = heap.poll()
    }
    while(!heap.isEmpty()){
        arr[i++] = heap.poll()
    }
}
let arr = [3,1,5,3,2,6,8]
sorteArrDistanceLessK(arr,4)
console.log(arr)
